package com.leetcode.ask;

/**
 * @ProjectName: leetcode
 * @Package: com.leetcode.ask
 * @description: 两数相加
 * 第2题
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * 示例：
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * @Author: liyc
 * @CreateDate: 2020/1/2 3:57 PM
 * @Version: 1.0
 * <p>Copyright: Copyright (c) 2020</p>
 */
public class AddTwoNumbers {

    /**
     * @param
     * @return
     * @description 官方解法
     * 复杂度：O(n) 一次循环
     * https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/
     * @author liyc
     * @date 2020/1/3
     */
    public static ListNode offical(ListNode l1, ListNode l2) {
        ListNode lt1 = l1;
        ListNode lt2 = l2;
        ListNode l3 = null;
        ListNode lt3 = null;
        ListNode tNode = null;
        int i = 0;
        //进位
        int add = 0;
        while (true) {
            if (lt1 == null && lt2 == null) {
                break;
            }
            if (i == 0) {
                int t = 0;
                if (lt1 != null) {
                    t += lt1.val;
                    lt1 = lt1.next;
                }
                if (lt2 != null) {
                    t += lt2.val;
                    lt2 = lt2.next;
                }
                if (t >= 10) {
                    l3 = new ListNode(t - 10);
                    add = 1;
                } else {
                    l3 = new ListNode(t);
                    add = 0;
                }
                tNode = l3;
            } else {

                int t = 0;
                if (lt1 != null) {
                    t += lt1.val;
                    lt1 = lt1.next;
                }
                if (lt2 != null) {
                    t += lt2.val;
                    lt2 = lt2.next;
                }
                if (add > 0) {
                    t += add;
                }
                if (t >= 10) {
                    lt3 = new ListNode(t - 10);
                    add = 1;
                } else {
                    lt3 = new ListNode(t);
                    add = 0;
                }
                tNode.next = lt3;
                tNode = lt3;
            }
            i++;
        }
        if (add > 0) {
            lt3 = new ListNode(add);
            tNode.next = lt3;
            tNode = lt3;
        }
        return l3;


    }


    /**
     * @param
     * @return
     * @description 思路 ：
     * @author liyc
     * @date 2020/1/2
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuffer l1Str = new StringBuffer();

        StringBuffer l2Str = new StringBuffer();
        while (l1 != null) {
            l1Str.append(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            l2Str.append(l2.val);
            l2 = l2.next;
        }
        char[] oneArr = l1Str.toString().toCharArray();
        char[] twoArr = l2Str.toString().toCharArray();
        int len = oneArr.length > twoArr.length ? oneArr.length : twoArr.length;
        boolean add = false;
        StringBuffer sumStr = new StringBuffer();
        for (int i = 0; i < len; i++) {
            int one = 0;
            if (i < oneArr.length) {
                one = oneArr[i] - 48;
            }
            int two = 0;
            if (i < twoArr.length) {
                two = twoArr[i] - 48;
            }
            int sum;
            if (add) {
                sum = one + two + 1;
            } else {
                sum = one + two;
            }
            if (sum >= 10) {
                add = true;
                sumStr.append(sum - 10);
            } else {
                add = false;
                sumStr.append(sum);
            }
        }
        //最后一位的1
        if (add) {
            sumStr.append(1);
        }
        char[] arrays = sumStr.toString().toCharArray();
        ListNode listNode = new ListNode(arrays[0] - 48);
        ListNode tempNode = listNode;
        for (int i = 1; i < arrays.length; i++) {
            char c = arrays[i];
            ListNode node = new ListNode(c - 48);
            tempNode.next = node;
            tempNode = node;
        }
        return listNode;

    }


    /**
     * @param
     * @return
     * @description 思路 ：有缺陷，超长字符串
     * @author liyc
     * @date 2020/1/2
     */
    public static ListNode addTwoNumbersTwo(ListNode l1, ListNode l2) {
        ListNode pre = null;
        ListNode next = null;

        while (l1 != null) {
            next = l1.next;
            l1.next = pre;
            pre = l1;
            l1 = next;
        }
        l1 = pre;

        pre = null;
        next = null;

        while (l2 != null) {
            next = l2.next;
            l2.next = pre;
            pre = l2;
            l2 = next;
        }
        l2 = pre;


        String l1Str = "";
        ListNode p = l1;
        while (p != null) {
            l1Str += p.val;
            p = p.next;
        }
        String l2Str = "";
        ListNode q = l2;
        while (q != null) {
            l2Str += q.val;
            q = q.next;
        }

        Long result = Long.valueOf(l1Str) + Long.valueOf(l2Str);
        String res = String.valueOf(result);

        ListNode resNode = null;
        ListNode m = null;
        char[] cs = res.toCharArray();
        for (int i = cs.length - 1; i >= 0; i--) {
            if (i == cs.length - 1) {
                resNode = new ListNode(cs[i] - 48);
                m = resNode;
            } else {
                ListNode t = new ListNode(cs[i] - 48);
                m.next = t;
                m = m.next;
            }

        }

        return resNode;

    }


    public static void main(String[] args) {

        ListNode listNode = new ListNode(2);
        listNode.next = new ListNode(4);
        listNode.next.next = new ListNode(3);

        ListNode listNode1 = new ListNode(5);
        listNode1.next = new ListNode(6);
        listNode1.next.next = new ListNode(4);

        offical(listNode, listNode1);

    }

    public static class ListNode {
        int val;
        ListNode next;

        public ListNode(int x) {
            val = x;
        }
    }

}


